/**
 * 堆
 * 2018年 12月 01日 星期六
 *
 * @author fireway
 */
class Node {
    private int mData;

    public Node(int data) {
        mData = data;
    }

    public void setData(int data) {
        mData = data;
    }

    public int getData() {
        return mData;
    }

    @Override
    public String toString() {
        return "{" + mData + "}";
    }
}

public class Heap {
    private Node[] mArray;

    private int mSize;

    public Heap(int initialCapacity) {
        mArray = new Node[initialCapacity];
        mSize = 0;
    }

    public boolean insert(int data) {
        if (isFull()) {
            System.out.println("Heap full!");
            return false;
        }
        Node node = new Node(data);
        mArray[mSize] = node;
        trickleUp(mSize);
        mSize++;
        return true;
    }

    private void trickleUp(int index) {
        Node tmp = mArray[index];
        int parent = (index - 1) / 2;

        while (index > 0 && mArray[parent].getData() < tmp.getData()) {
            mArray[index] = mArray[parent];
            index = parent;
            parent = (index - 1) / 2;
        }

        mArray[index] = tmp;
    }

    public boolean isFull() {
        return mArray.length == mSize;
    }

    public boolean isEmpty() {
        return 0 == mSize;
    }

    public void display() {
        System.out.print("array of heap: ");
        for (int i = 0; i < mSize; i++) {
            if (mArray[i] != null) {
                System.out.print(mArray[i].getData() + " ");
            } else {
                System.out.print("-- ");
            }
        }
        System.out.println();
        String dots = "...............................";
        System.out.println(dots+dots);
        int column = 0;
        int nBlanks = 32;
        int nItemsPerRow = 1;
        for (int i = 0; i < mSize; i++) {
            if (column == 0) {
                for (int j = 0; j < nBlanks; j++) {
                    System.out.print(' ');
                }
            }
            System.out.print(mArray[i].getData());

            if (++column == nItemsPerRow) {
                nBlanks /= 2;
                nItemsPerRow *= 2;
                column = 0;
                System.out.println();
            } else {
                for (int j = 0; j < nBlanks * 2 - 2; j++) {
                    System.out.print(' ');
                }
            }
        }
        System.out.println("\n"+dots+dots);
    }

    public Node remove() {
        if (isEmpty()) {
            System.out.println("Heap empty!");
            return null;
        }
        Node root = mArray[0];
        mArray[0] = mArray[mSize - 1];
        mArray[mSize - 1] = null;
        mSize--;
        trickleDown(0);
        return root;
    }

    private void trickleDown(int currentIndex) {
        Node tmp = mArray[currentIndex];

        int index = currentIndex;
        // while ((index * 2 + 1) <= (mSize - 1)) {
        while (index < (mSize - 1) / 2) {
            int leftChild = index * 2 + 1;
            int rightChild = leftChild + 1;

            int largerChild = 0;
            if (mArray[rightChild] == null || (mArray[leftChild].getData() > mArray[rightChild].getData())) {
                largerChild = leftChild;
            } else {
                largerChild = rightChild;
            }

            if (tmp.getData() >= mArray[largerChild].getData()) {
                break;
            }
            mArray[index] = mArray[largerChild];
            index = largerChild;
        }

        mArray[index] = tmp;
    }

    public boolean change(int index, int newValue) {
        if (index < 0 || index > mSize - 1) {
            System.out.println("heap index error: " + index);
            return false;
        }

        int oldValue = mArray[index].getData();
        mArray[index].setData(newValue);
        if (newValue > oldValue) {
            trickleUp(index);
        } else {
            trickleDown(index);
        }

        return true;
    }
}
